package com.easy.carl.algorithm.array.doublePoint;

import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Deque;
import java.util.stream.Collectors;

public class BackspaceCompare844 {

    //栈存储
    public boolean backspaceCompare(String s, String t) {
        return help(s).equals(help(t));
    }

    public String help(String str){
        char[] chars = str.toCharArray();
        Deque q = new ArrayDeque<>();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i]=='#'){
               if (!q.isEmpty()){
                   q.pop();
               }
            }else {
                q.push(chars[i]);
            }
        }
        return q.toString();
    }

    //双指针
    public boolean backspaceCompare1(String s, String t){
        int i=s.length()-1;
        int j=t.length()-1;
        int sSkip=0;
        int tSkip=0;
        while (i>=0||j>=0){
            //根据规则，找最后一个字符
            while (i>=0) {
                if (s.charAt(i) == '#') {
                    sSkip++;
                    i--;
                } else if (sSkip > 0) {
                    i--;
                    sSkip--;
                }else {
                    break;
                }
            }
            //根据规则，找最后一个字符
            while (j>=0){
                if (t.charAt(j) == '#') {
                    tSkip++;
                    j--;
                } else if (tSkip > 0) {
                    j--;
                    tSkip--;
                }else {
                    break;
                }
            }
            if (i>=0&&j>=0){
                if (s.charAt(i)==t.charAt(j)) {
                    i--;
                    j--;
                }else {
                    return false;
                }
            }else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
        }
        return true;
    }




    public static void main(String[] args) {
        BackspaceCompare844 backspaceCompare844 = new BackspaceCompare844();
        System.out.println(backspaceCompare844.backspaceCompare1("xywrrmp","xywrrmu#p"));;

    }
}
